

// 全排列1：给写一个无重复数字的序列，返回所有可能的结果

int  **res;	//保存排列结果
int *path, *used;
int pathlen, cnt;
void backtrack(int arr[], int len, int** returnColumnSizes)
{
	if (pathlen == len) {	//完成一次排列
        res[cnt] = malloc(sizeof(int) * len);
        memcpy(res[cnt], path, sizeof(int) * len);
        (*returnColumnSizes)[cnt] = len;
		cnt++;
		return ;
	}

	for (int i = 0; i < len; i++) {	//横向遍历
		if (used[i]) continue;	// 已被选择

		path[pathlen++] = arr[i]; // 选择数字
		used[i] = 1;

		backtrack(arr, len, returnColumnSizes);	//纵向遍历

		used[i] = 0; // 撤销选择，回溯上一步
		pathlen--;
	}
}


int factorial(int x) {
	if (x <= 1) return 1;
	else return x*factorial(x-1);
}
// int cmp(const void *a, const void *b) {
// 	return *(int *)a - *(int *)b;
// }

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{	
    // 先排序，方便去重
	//qsort(nums, numsSize, sizeof(int), cmp);
    
    int N = factorial(numsSize);    // N种结果
	res = malloc(sizeof(int *) * N);	//全局变量
    *returnColumnSizes = malloc(sizeof(int) * N);

	path = malloc(sizeof(int)*numsSize);	//保存解
	used = calloc(numsSize, sizeof(int));	//标识该位置上的数字已使用
	cnt = 0; pathlen = 0;

	backtrack(nums, numsSize, returnColumnSizes);
    *returnSize = cnt;
    return res;
}


// 全排列2：给写一个数字序列，返回所有可能的结果，结果不能有重复

// 在for选择里添加如下行，即在同一level中，一个数值只能被选中一次
// if (i > 0 && arr[i] == arr[i-1] && !used[i-1])  continue; 


// 剑指offer-38：字符串的排列，同全排列2